package com.ubing.boot.notesforjava.test.leetcode;

import lombok.ToString;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.stream.Collectors;

public class BuildTree {
//    int[] preorder;
//    HashMap<Integer, Integer> dic = new HashMap<>();
//    public TreeNode buildTree(int[] preorder, int[] inorder) {
//        for(int i = 0; i < inorder.length; i++)
//            dic.put(inorder[i], i);
//        return myBuild(0, 0, inorder.length - 1);
//    }
//
//    private TreeNode myBuild(int root, int left, int right){
//        if(left > right) return null;
//        TreeNode node = new TreeNode(preorder[root]);          // 建立根节点
//        int i = dic.get(preorder[root]);                       // 划分根节点、左子树、右子树
//        node.left = myBuild(root + 1, left, i - 1);              // 开启左子树递归
//        node.right = myBuild(root + i - left + 1, i + 1, right); // 开启右子树递归
//        return node;
//    }




    List<Integer> preorder;
    List<Integer> inorder;
    public TreeNode buildTreeAsList(int[] preorder, int[] inorder) {
        this.preorder = Arrays.stream(preorder).boxed().collect(Collectors.toList());
        this.inorder = Arrays.stream(inorder).boxed().collect(Collectors.toList());
        return myBuildAsList(0, 0, inorder.length - 1);
    }

    private TreeNode myBuildAsList(int root, int left, int right){
        if(left > right) return null;
        TreeNode node = new TreeNode(preorder.get(root));          // 建立根节点
        int i = inorder.indexOf(preorder.get(root));                       // 划分根节点、左子树、右子树
        node.left = myBuildAsList(root + 1, left, i - 1);              // 开启左子树递归
        node.right = myBuildAsList(root + i - left + 1, i + 1, right); // 开启右子树递归
        return node;
    }
    @ToString
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public static void main(String[] args) {
        BuildTree buildTree = new BuildTree();
        TreeNode treeNode = buildTree.buildTreeAsList(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7});
        System.out.println(treeNode);
    }
}

